package codingforgreat.class10;

public class Class05_BooleanEvaluation {

    public class Info{
        public int t;
        public int f;

        public Info(int t, int f) {
            this.t = t;
            this.f = f;
        }
    }
    public int countEval(String s, int result) {
        if(s == null || s == ""){
            return 0;
        }
        Info[][] dp = new Info[s.length() + 1][s.length() + 1];
        char[] str = s.toCharArray();
        Info allInfo = process(str, 0, str.length-1,dp);
        return result == 1 ? allInfo.t : allInfo.f;
    }

    public Info process(char[] str,int L,int R,Info[][] dp){
        if(dp[L][R] != null){
            return dp[L][R];
        }
        Info res;
        if(L == R){
           int t = str[L] == '1' ? 1 : 0;
           int f = str[L] == '0' ? 1 : 0;
           res =  new Info(t,f);
           dp[L][R] = res;
           return res;
        }
        int t = 0;
        int f = 0;
        for (int i = L + 1; i <R; i+=2) {
            Info left = process(str,L,i - 1,dp);
            Info right = process(str,i + 1,R,dp);
            int leftTrue = left.t;
            int leftFalse = left.f;
            int rightTrue = right.t;
            int rightFalse = right.f;
            switch (str[i]) {
                case '&':
                    t += leftTrue * rightTrue;
                    f += leftFalse * rightTrue + leftTrue * rightFalse +  leftFalse * rightFalse;
                    break;
                case '|':
                    t += leftTrue*rightTrue + leftFalse * rightTrue + leftTrue * rightFalse;
                    f += leftFalse * rightFalse;
                    break;
                case '^':
                    t += leftTrue*rightFalse + leftFalse*rightTrue;
                    f += leftFalse*rightFalse + leftTrue * rightTrue;
                    break;
            }
        }
        res = new Info(t,f);
        dp[L][R] = res;
        return res;
    }
}
